#include <iostream>
#include <algorithm>
#include <cassert>
using namespace std;

int find(int num[], int r, int x) {
	int len = r + 1;
	int l = 0;
	while (len > 0)
	{
		int half = len / 2;
		int mid = l;
		mid += half;
		if (num[mid] < x) {
			l = mid + 1;
			len = len - half - 1;
		}
		else
			len = half;
	}
	return l;
}

int main()
{
	int n;
	cin >> n;
	int *res = new int[n];
	for (int i = 0; i < n; i++)
	{
		int m;
		cin >> m;
		int *nums = new int[m];
		int lis[40000 + 6];
		int cnt = 1, k = 0;
		for (int j = 0; j < m; j++)
		{
			cin >> nums[j];
		}
		lis[0] = nums[0];
		for (int j = 1; j < m; j++)
		{
			if (nums[j] > lis[k])
			{
				lis[k + 1] = nums[j];
				k++;
				cnt++;
			}
			else
			{
				int b = my_lower_bound(lis, k, nums[j]);
				assert(b <= k);
				lis[b] = nums[j];
			}
		}
		res[i] = cnt;
		delete[] nums;
	}
	for (int i = 0; i < n; i++)
	{
		cout << res[i] << endl;
	}
	delete[] res;
	return 0;
}
